package pro.softzhang.algo.lc600;

import pro.softzhang.algo.flag.knowledge.KPrefixTree;

/**
 *
 */
@KPrefixTree
public class LC677_MapSumPairs {
    public static void main(String[] args) {

    }

    static
    class MapSum {
        private TrieNode root;

        public MapSum() {
            root = new TrieNode();
        }

        public void insert(String key, int val) {
            TrieNode node = root;
            for (int i = 0; i < key.length(); i++) {
                char ch = key.charAt(i);
                if(node.children[ch - 'a'] == null) {
                    node.children[ch - 'a'] = new TrieNode();
                }
                node = node.children[ch - 'a'];
            }
            node.value = val;
        }

        public int sum(String prefix) {
            TrieNode node = root;
            for (int i = 0; i < prefix.length(); i++) {
                char ch = prefix.charAt(i);
                if(node.children[ch - 'a'] == null)
                    return 0;
                node = node.children[ch - 'a'];
            }

            return doSum(node);
        }

        private int doSum(TrieNode node) {
            if(node == null)
                return 0;

            int sum = node.value;
            for (TrieNode child : node.children) {
                sum += doSum(child);
            }
            return sum;
        }

        static class TrieNode {
            public TrieNode[] children;
            public int value;

            public TrieNode() {
                children = new TrieNode[26];
            }
        }
    }
}